﻿//#define IGN_BARR

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

using alib.Array;
using alib.Collections;
using alib.Debugging;
using alib.Enumerable;

namespace alib.dg
{
	using Array = System.Array;
	using String = System.String;
	using Enumerable = System.Linq.Enumerable;

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public struct layout_entry
	{
		public layout_entry(int ix_physical, Vref vr)
			: this()
		{
			this._ix_logical = this.ix_physical = ix_physical;
			this.vr = vr;
		}

		public Vref vr;

		public bool f_proxy;

		public int ix_physical;

		int _ix_logical;
		public int ix_logical { get { return _ix_logical; } }

		public int[] Upper, Lower;

		public bool IsTop { get { return Upper.Length == 0; } }

		public bool IsLeaf { get { return Lower.Length == 0; } }

		public int _swap_logical_index(int i_new)
		{
			int i_old = this._ix_logical;
			this._ix_logical = i_new;
			return i_old;
		}

		/// <summary>
		/// returns the LOGICAL median of this vertex with respect to the neighboring layer. This value
		/// is not any kind of index in this vertex's *own* layer, that is, it only has meaning in
		/// relation to other logical median values obtained between the same two layers
		/// </summary>
		public int median_from_above(layout_level _this_lev)
		{
			Debug.Assert(!this.IsTop);
			return _this_lev.PrevLevel.log_median_from_phys(Upper);
		}

		public int median_from_below(layout_level _this_lev)
		{
			Debug.Assert(!this.IsLeaf);
			return _this_lev.NextLevel.log_median_from_phys(Lower);
		}

		public String map_above_display(layout_level _this_lev)
		{
			return _this_lev.IsTopLevel ? "" : mappings(_this_lev.PrevLevel, this.Upper);
		}
		public String map_below_display(layout_level _this_lev)
		{
			return _this_lev.IsBottomLevel ? "" : mappings(_this_lev.NextLevel, this.Lower);
		}
		String mappings(layout_level _other_lev, int[] arr_phys)
		{
			String s = "";
			for (int i = 0; i < arr_phys.Length; i++)
			{
				if (i > 0)
					s += " ";
				var ixp = arr_phys[i];
				s += String.Format("{0}→{1}", ixp, _other_lev.arr[ixp].ix_logical);
			}
			return s;
		}
		public String _disp()
		{
			return String.Format("logical:{0,3} {1,5} V{2}", ix_logical, "[" + ix_physical + "]", (int)vr);
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// One 'level' or layer of a dag which has (i.e. longest-path) levels assigned.
	/// This object maintains a fixed number of verticies in a fixed physical order, which corresponds to the
	/// position of 'n' layout_entry structs in 'this.arr.' Each layout_entry contains an index which establishes
	/// a logical ordering for this layer, and this class maintains a reverse index of these values
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public class layout_level : IReadOnlyList<int>, IComparer<int>
	{
		public static readonly int[] NoEdges = Collection<int>.None;

		public layout_level(layouter layouter, int i_level, int c_alloc)
		{
			this.layouter = layouter;
			this.i_level = i_level;
			this.arr = new layout_entry[c_alloc];
			this.log2phys = new int[c_alloc];

			_debug_init();
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly layouter layouter;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly layout_entry[] arr;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int[] log2phys;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly int i_level;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public int c_edges_above, c_edges_below;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool IsTopLevel { [DebuggerStepThrough] get { return i_level == 0; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool IsBottomLevel { [DebuggerStepThrough] get { return i_level == layouter.levels.Length - 1; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public layout_level PrevLevel { [DebuggerStepThrough] get { return IsTopLevel ? null : layouter.levels[i_level - 1]; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public layout_level NextLevel { [DebuggerStepThrough] get { return IsBottomLevel ? null : layouter.levels[i_level + 1]; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool HasLogicalOrder
		{
			get
			{
				for (int i = 0; i < log2phys.Length; i++)
					if (log2phys[i] != i)
						return true;
				return false;
			}
		}

		public int[] convert_to_logical(int[] rg_phys)
		{
			int c = rg_phys.Length;
			if (c == 0)
				return NoEdges;
			if (c == 1)
				return new[] { arr[rg_phys[0]].ix_logical };

			var rg_log = new int[c];
			for (int i = 0; i < c; i++)
				rg_log[i] = arr[rg_phys[i]].ix_logical;

			Array.Sort(rg_log);
			return rg_log;
		}

		public int log_median_from_phys(int[] rg_phys)
		{
			int ix;
			if ((ix = rg_phys.Length) == 1)
				return arr[rg_phys[0]].ix_logical;

#if stupid_because_picking_the_other_median_doesnt_change_the_order
			if (ix >= 4 && (ix & 1) == 0)
			{
				int left_ix = ix - 1 >> 1;
				Array.Sort(rg_phys, this);
				//var _left_logical = rg_phys.Select(pp => arr[pp].ix_logical).ToArray();
				//alib.Math._math_ext.SelectMedian(rg_phys, left_ix, this);

				var left_avg = rg_phys.Take(left_ix).Select(pp => arr[pp].ix_logical).Average();
				var right_avg = rg_phys.Skip(left_ix + 2).Select(pp => arr[pp].ix_logical).Average();
				int left_m = arr[rg_phys[left_ix]].ix_logical;
				int right_m = arr[rg_phys[left_ix + 1]].ix_logical;
				return left_m - left_avg < right_avg - right_m ? left_m : right_m;
			}
#endif

			ix >>= 1;
			alib.Math._math_ext.SelectMedian(rg_phys, ix, this);
			return arr[rg_phys[ix]].ix_logical;
		}

		///////////////////////////////////////////////////////////
		/// 
		public void cache_neighbors()
		{
			/// as a precaution just-in-case; finish initializing the log/phys map before 
			/// letting the entry do its caching (as opposed to doing both in a single loop)
			for (int i = 0; i < arr.Length; i++)
			{
				log2phys[arr[i].ix_logical] = i;
				Debug.Assert(log2phys[arr[i].ix_logical] == i);
			}

			for (int i = 0; i < arr.Length; i++)
				_cache_neighbors(ref arr[i]);
		}

		void _cache_neighbors(ref layout_entry ent)
		{
			var g = (dg)layouter.graph;
			Vref[] vnbr;

			if (IsTopLevel || 0 == (vnbr = g.vertex_parents_distinct(ent.vr)).Length)
				ent.Upper = NoEdges;
			else
				c_edges_above += (ent.Upper = PrevLevel._create_cache_arr(vnbr)).Length;

			if (IsBottomLevel || 0 == (vnbr = g.vertex_children_distinct(ent.vr)).Length)
				ent.Lower = NoEdges;
			else
				c_edges_below += (ent.Lower = NextLevel._create_cache_arr(vnbr)).Length;
		}

		int[] _create_cache_arr(Vref[] arr_of_vref)
		{
			Debug.Assert(arr_of_vref.IsDistinct());

			int c = arr_of_vref.Length;
			if (c == 0)						/// leaf vertex which is not on the bottom layer
				return NoEdges;

			int[] cache = new int[c];
			int j = 0;
			for (int i = 0; i < c; i++)
			{
				Vref vr = arr_of_vref[i];
				if (layouter.ignore_vertex(vr))
					continue;
				vref_ix vx = layouter.vref_index[vr];

				/// if you hit this assert then perhaps verticies are not in adjacent layers as they should be.
				//Debug.Assert(vx.i_level == this.i_level && this.arr[vx.ix_phys].vr == vr);
				if (vx.i_level != this.i_level || this.arr[vx.ix_phys].vr != vr)
					continue;

				cache[j++] = vx.ix_phys;
			}
			if (j < c)
			{
				cache = alib.Array.arr.Resize(cache, j);
				layouter.c_missing_edge_proxies += c - j;
			}
			return cache;
		}
		/// 
		///////////////////////////////////////////////////////////


		///////////////////////////////////////////////////////////
		/// <summary> The main layout-establishing operation.
		/// use this instead of accessing 'ix_logical' to
		/// ensure that the logical-to-physical mappings remain 
		/// internally consistent </summary>
		public bool SetLogicalIndex(int ix_phys, int ix_log)
		{
			int ixl;
			if (ix_log == (ixl = arr[ix_phys]._swap_logical_index(ix_log)))
				return false;

			var ixp = log2phys[ix_log];
			log2phys[ix_log] = ix_phys;

			//Debug.Print("[L{0}.{1}]→{2}  [L{0}.{3}]→{4}", i_level, ix_phys, ix_log, ixp, ixl);

			ix_phys = arr[ixp]._swap_logical_index(ixl);
			log2phys[ixl] = ixp;
			return true;
		}
		/// <summary> Sets the LOGICAL order to the order which is implicit in the 
		/// sequence of PHYSICAL indexes in the specified array </summary>
		public bool SetLogicalOrder(int[] rg_phys)
		{
			Debug.Assert(rg_phys.ToHashSet().SetEquals(Enumerable.Range(0, Count)));
			bool f_any = false;
			for (int ixl = 0; ixl < rg_phys.Length; ixl++)
				f_any |= ixl != arr[rg_phys[ixl]]._swap_logical_index(ixl);

			if (f_any)
			{
				log2phys = rg_phys;
				//Debug.Print("set L{0}: {1}", i_level, _log_order);
			}
			return f_any;
		}
		/// 
		///////////////////////////////////////////////////////////

		//public static bool IsSortedByKeys(int[] keys, int[] data)
		//{
		//	Debug.Assert(keys.Length == data.Length);
		//	int i = 0, k = -1;
		//	while (i < data.Length)
		//		if (k > (k = keys[data[i++]]))
		//			return false;
		//	return true;
		//}
		public static bool IsSorted(int[] data)
		{
			int i = 0, k = -1;
			while (i < data.Length)
				if (k > (k = data[i++]))
					return false;
			return true;
		}

		public bool set_medians_from_above()
		{
			if (this.Count == 1 || this.IsTopLevel || PrevLevel.Count == 1)
				return false;

			return renormalize_logical(arr.Select(le => le.IsTop ? -1 : le.median_from_above(this)));
		}

		public bool set_medians_from_below()
		{
			if (this.Count == 1 || this.IsBottomLevel || NextLevel.Count == 1)
				return false;

			return renormalize_logical(arr.Select(le => le.IsLeaf ? -1 : le.median_from_below(this)));
		}

		bool renormalize_logical(IEnumerable<int> _order)
		{
			var _tmp = _order as int[] ?? _order.ToArray();
			if (IsSorted(_tmp))
				return false;

			int c = Count;
			var _new = new int[c];
			for (int i = 0; i < c; i++)
				_new[i] = i;
			Array.Sort(_tmp, _new);
			return SetLogicalOrder(_new);
		}
#if false
		int add_work_ixs(int[] work, int k, int[] rg_phys)
		{
			Debug.Assert(k + rg_phys.Length <= work.Length);
			int c = rg_phys.Length;
			if (c == 1)
				work[k++] = arr[rg_phys[0]].ix_logical;
			else if (c > 1)
			{
				rg_phys = convert_to_logical(rg_phys);
				for (int j = 0; j < c; j++)
					work[k++] = rg_phys[j];
			}
			return c;
		}

		public int crossings_below()
		{
			if (this.IsBottomLevel)
				return 0;

			int i, k;
			for (i = 0, k = 0; i < arr.Length; i++)
				k += arr[i].Lower.Length;
			if (k <= 1)
				return 0;

			int[] work = new int[k];

			for (i = 0, k = 0; i < arr.Length; i++)
				k += NextLevel.add_work_ixs(work, k, arr[log2phys[i]].Lower);

			return insertion_cost(work);
		}

		int insertion_cost(int[] work)
		{
			Debug.Assert(work.Length > 1);
			int i, j, prv, cur, tmp;
			int cost = 0;
			prv = work[0];
			for (i = 1; i < work.Length; i++)
			{
				if (prv <= (cur = work[i]))
					prv = cur;
				else
				{
					work[j = i] = prv;
					while (--j > 0 && (tmp = work[j - 1]) > cur)
					{
						work[j] = tmp;
						if (j == 0)
							break;
					}
					work[j] = cur;
					cost += i - j;
				}
			}
			return cost;
		}
#else
		unsafe void add_work_ixs(int** pp, int[] rg)
		{
			int c = rg.Length;
			if (c == 1)
				*(*pp)++ = arr[rg[0]].ix_logical;
			else if (c > 1)
			{
				rg = convert_to_logical(rg);
				for (int j = 0; j < c; j++)
					*(*pp)++ = rg[j];
			}
		}

		public unsafe int crossings_below()
		{
			if (arr == null || c_edges_below <= 1)
				return 0;

			int* work = stackalloc int[c_edges_below];
			int* fill = work;
			for (int i = 0; i < arr.Length; i++)
			{
				var rg = arr[log2phys[i]].Lower;
				if (rg == null)
					return 0;
				NextLevel.add_work_ixs(&fill, rg);
			}

			return reordering_cost(work, c_edges_below);
		}

		static unsafe int reordering_cost(int* work, int c)
		{
			Debug.Assert(c > 1);

			int* pi = work, pc = work + c;
			int v = *pi, cost = 0;
			while (++pi < pc)
				if (v <= *pi)
					v = *pi;
				else
				{
					int* pj = pi - 1;
					while (pj > work && *(pj - 1) > *pi)
						*pj = *--pj;
					*pj = *pi;
					*pi = v;
					cost += (int)(pi - pj);
				}
			return cost;
		}
#endif

		///////////////////////////////////////////////////////////
		/// <summary>
		/// This object's enumerator implmentation enumerates the layout_entrys by emitting their PHYSICAL indexes 
		/// in the current LOGICAL order.
		/// </summary>
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public int Count { [DebuggerStepThrough] get { return arr.Length; } }

		public int this[int ix_logical] { get { return log2phys[ix_logical]; } }

		public IEnumerator<int> GetEnumerator()
		{
			for (int ix_logical = 0; ix_logical < arr.Length; ix_logical++)
				yield return log2phys[ix_logical];
		}
		IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
		///
		///////////////////////////////////////////////////////////


		///////////////////////////////////////////////////////////
		/// <summary>
		/// implement a comparer which sorts PHYSICAL indexes according to this layer's current LOGICAL order.
		/// This allows the layout_entry to use its owner/array as the comparer for the median computations.
		/// </summary>
		public int Compare(int x, int y) { return arr[x].ix_logical - arr[y].ix_logical; }
		///
		///////////////////////////////////////////////////////////


		public override String ToString()
		{
			return String.Format("LEVEL {0} -- verticies: {1} -- crossings: {2} {3}",
				i_level,
				this.Count,
				crossings_below(),
				HasLogicalOrder ? "LOG" : "PHYS");
		}

#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public debug_layout_entry[] _debug_entries;

		void _debug_init()
		{

			this._debug_entries = new debug_layout_entry[arr.Length];
			for (int i = 0; i < arr.Length; i++)
				_debug_entries[i] = new debug_layout_entry(this, i);
		}
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		String _log_order
		{
			get { return log2phys.StringJoin(" ") + " -- " + log2phys.Select(phys => "V" + (int)arr[phys].vr).StringJoin(" "); }
		}
		[DebuggerDisplay("{_phys_order,nq}", Name = "Physical Order:")]
		String _phys_order { get { return arr.Select((e, ix) => String.Format("[{0}]V{1}", ix, (int)e.vr)).StringJoin(" "); } }
		[DebuggerDisplay("{PrevLevel==null?\"\":PrevLevel.ToString(),nq}", Name = "Previous Level")]
		layout_level _y_prev { get { return PrevLevel; } }
		[DebuggerDisplay("{NextLevel==null?\"\":NextLevel.ToString(),nq}", Name = "Next Level")]
		layout_level _z_next { get { return NextLevel; } }
		[DebuggerDisplay("{_log_order,nq}", Name = "Logical Order:")]
		String[] _log_order_map { get { return log2phys.Select(phys => arr[phys]._disp()).ToArray(); } }
#else
		[Conditional("DEBUG")]
		void _debug_init() { }
#endif
	};


	/////////////////////////////////////////////////////////////
	/// 
	[DebuggerDisplay("level: {i_level}  ix_phys: {ix_phys}")]
	public struct vref_ix
	{
		public int i_level;
		public int ix_phys;
	};
	/// 
	/////////////////////////////////////////////////////////////


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// Main dag layout controller class
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public class layouter
	{
		public layouter(IStringGraph graph)
		{
			//var rwg = graph as rw_graph;
			//if (rwg == null)
			//	throw new Exception();

			this.graph = ((rw_string_graph)graph).deep_copy();

			//var rwg = graph as rw_string_graph;
			//this.graph = rwg != null ? rwg.deep_copy() : new rw_string_graph(graph);
			//this.graph = graph;

			start();
		}

		//public readonly rw_string_graph graph;
		public readonly IStringGraph graph;

		/// <summary> as usual, the main data structure is an array of structs.
		/// be careful not to inadvertently 'lift' or 'box' it </summary>
		public layout_level[] levels;

		/// <summary>
		/// index from graph-native vertex values (Vref) into the level/physical index tuple. Convenient, and used 
		/// during initialization, but currently does not have an important role in the layout operation proper.
		/// </summary>
		public vref_ix[] vref_index;

		int max_level;
		int dummy_v, dummy_e;

		public int c_missing_edge_proxies;

		//public IEnumerable<Vref> layout_verticies()
		//{
		//	foreach (var vr in ((dg)graph).verticies)
		//		if (!is_layout_proxy_vref(vr))
		//			yield return vr;
		//}

		public bool is_layout_proxy_vref(Vref vr) { return !graph.Verticies[vr].IsFree && graph.Verticies[vr].value == dummy_v; }

		//public bool is_layout_source_vref(Vref vr) { return !graph.Verticies[vr].IsFree && ((dg)graph).vertex_value(vr) != dummy_v; }

		//public bool is_deleted_source_vref(Vref vr) { return vr >= vref_index.Length || vref_index[vr].i_level == -1; }
		//public bool is_deleted_source_vref(Vref vr) { return vr >= vref_index.Length || graph.Verticies[vr].value == dummy_v; }


		/////////////////////////////////////////////////////////////
		/// 
		void start()
		{
			graph.check();

			this.dummy_v = ((rw_string_graph)graph).vdict.Add("XV");
			this.dummy_e = ((rw_string_graph)graph).edict.Add("XE");

			//remove_monovertex_chains();

			find_levels();
			while (insert_edge_proxies())
				find_levels();

			graph.check();

			var lev_counts = get_level_counts();

			initialize_layers(lev_counts);

			cache_adjacent_layer_nodes();

			median_sweeps();

			//restore_ignored_verticies();

			graph.check();

			Debug.Print(graph.ToString());
			Debug.Print(report());
		}
		/// 
		/////////////////////////////////////////////////////////////

#if IGN_BARR
		BitArray.BitArr _ign_vtx;
		public bool ignore_vertex(Vref vr)
		{
			return _ign_vtx != null && vr < _ign_vtx.Count && _ign_vtx[vr];
		}
		void restore_ignored_verticies()
		{
			if (_ign_vtx == null)
				return;
			//foreach (int ix in _ign_vtx.OnesPositions())
			//{
			//	Vref vr = new Vref(ix);
			//}
		}
#else
		public bool ignore_vertex(Vref vr) { return false; }
		void restore_ignored_verticies() { }
#endif

		void remove_monovertex_chains()
		{
#if IGN_BARR
			_ign_vtx = new BitArray.BitArr(graph.VertexAlloc);
#endif
			foreach (var vr in ((dg)graph).leaves)
				trim_up_chain(vr);
		}

		void trim_up_chain(Vref vcur)
		{
			Vref[] vpar;
			while (!ignore_vertex(vcur) && (vpar = ((dg)graph).vertex_parents_distinct(vcur)).Length == 1)
			{
				var x = ((dg)graph).vertex_children_distinct(vpar[0]);
				Debug.Assert(x.Length > 0);
				if (x.Length == 1)
					Debug.Assert(x[0] == vcur);

#if IGN_BARR
				if (_ign_vtx != null)
					_ign_vtx[vcur] = true;
#else
				graph.delete_all_in_edges(vcur);
				graph.delete_vertex(vcur);
#endif
				if (x.Length > 1)
					break;

				vcur = vpar[0];
			}
		}

		bool insert_edge_proxies()
		{
			int c_vadded = 0;
			bool f_more = false;

			/// ce_sav: where to stop, since any edges we add during this loop may point to vertexes
			/// which are not in the vref_index. Accordingly, 'insert_edge_proxies' must be called
			/// repeatedly until it reports no new vertexes.
			int ce_sav = graph.EdgeAlloc;

			for (Eref er = Eref.Zero; er < ce_sav; er++)
			{
				if (!graph.edge_is_valid(er))
					continue;

				Vref v_from = graph.Edges[er].v_from, v_to = graph.Edges[er].v_to;

				if (v_from >= vref_index.Length || v_to >= vref_index.Length)
				{
					f_more = true;
					continue;
				}

				if (ignore_vertex(v_from) || ignore_vertex(v_to))
					continue;

				int L0 = vref_index[v_from].i_level;
				int L1 = vref_index[v_to].i_level;
				if (L0 < 0 || L1 < 0)
				{
					f_more = true;
					continue;
				}
				int delta = L1 - L0;
				if (delta < 0)
				{
					throw new Exception("??");
				}

				if (delta > 1)
				{
					graph.delete_edge(er);

					while (++L0 < L1)
					{
						var v_new = graph.add_vertex(dummy_v);
						c_vadded++;
						graph.create_edge(v_from, v_new, dummy_e);
						v_from = v_new;
					}
					graph.create_edge(v_from, v_to, dummy_e);
					er--;
					f_more = true;
				}
			}

			Debug.Print("inserted {0} proxy verticies", c_vadded);
			return f_more;
		}

		int allocate_vref_index()
		{
			int c = graph.VertexAlloc;
			this.vref_index = new vref_ix[c];
			for (Vref vr = Vref.Zero; vr < c; vr++)
				this.vref_index[vr].i_level = -1;
			return c;
		}

		int find_levels()
		{
			int c = allocate_vref_index();
			this.max_level = 0;

			for (Vref vr = Vref.Zero; vr < c; vr++)
				if (vref_index[vr].i_level == -1 && graph.vertex_is_valid(vr) && graph.vertex_is_leaf(vr))
					get_level(vr);

			return max_level + 1;
		}

		int get_level(Vref vr)
		{
			int pl, lev;
			if ((lev = vref_index[vr].i_level) == -1)
			{
				if (!graph.vertex_is_top(vr))
					foreach (var f in ((dg)graph).vertex_parents(vr))
						if ((pl = get_level(f)) > lev)
							lev = pl;
				if ((vref_index[vr].i_level = ++lev) > max_level)
					max_level = lev;
			}
			return lev;
		}

		int[] get_level_counts()
		{
			var rgc = new int[max_level + 1];
			int lev;
			for (Vref vr = Vref.Zero; vr < vref_index.Length; vr++)
				if ((lev = vref_index[vr].i_level) != -1 /*&& !ignore_vertex(vr)*/)
					rgc[lev]++;
			return rgc;
		}

		void initialize_layers(int[] lev_counts)
		{
			int i;
			this.levels = new layout_level[max_level + 1];
			for (i = 0; i < levels.Length; i++)
				levels[i] = new layout_level(this, i, lev_counts[i]);

			for (Vref vr = new Vref(vref_index.Length - 1); vr >= 0; vr--)
			{
				if (!graph.vertex_is_valid(vr) /* || ignore_vertex(vr)*/)
					continue;

				int i_level = vref_index[vr].i_level;
				int ix_phys = vref_index[vr].ix_phys = --lev_counts[i_level];

				var lev_arr = levels[i_level].arr;

				lev_arr[ix_phys] = new layout_entry(ix_phys, vr);
			}
		}

		void cache_adjacent_layer_nodes()
		{
			c_missing_edge_proxies = 0;

			for (int i = 0; i < levels.Length; i++)
				levels[i].cache_neighbors();

			if (c_missing_edge_proxies > 0)
				Debug.Print("warning: missing {0} edge proxies. edges between non-adjacent layout levels will not affect layout.", c_missing_edge_proxies);
		}

		void median_sweeps()
		{
			int iter = 0;
			int cc_up = -1, cc_up_prev;
			int cc_dn = -1, cc_dn_prev;
			do
			{
				cc_up_prev = cc_up;
				cc_dn_prev = cc_dn;

				iter++;
				median_sweep_upwards();
				cc_up = total_crossings();
				Debug.Print("{0,3} [up]   crossings: {1,4}", iter, cc_up);

				iter++;
				median_sweep_downwards();
				cc_dn = total_crossings();
				Debug.Print("{0,3} [down] crossings: {1,4}", iter, cc_dn);
			}
			while (iter < 200 && (cc_up != cc_up_prev || cc_dn != cc_dn_prev));

			if (cc_up < cc_dn)
				median_sweep_upwards();
		}

		bool median_sweep_downwards()
		{
			bool f_any = false;
			for (int i = 1; i < levels.Length; i++)
				f_any |= levels[i].set_medians_from_above();
			return f_any;
		}

		bool median_sweep_upwards()
		{
			bool f_any = false;
			for (int i = levels.Length - 2; i >= 0; i--)
				f_any |= levels[i].set_medians_from_below();
			return f_any;
		}

		int total_crossings()
		{
			int sum = 0;
			for (int i = 0; i < levels.Length - 1; i++)
				sum += levels[i].crossings_below();
			return sum;
		}

		public String report()
		{
			var sb = new System.Text.StringBuilder();
			sb.AppendLine(this.ToString());
			for (int i = 0; i < levels.Length; i++)
				sb.AppendLine(levels[i].ToString());
			return sb.ToString();
		}

		public override String ToString()
		{
			if (levels == null)
				return "layout levels not initialized";
			return String.Format("LAYOUTER === verticies: {0} -- edges: {1} -- levels: {2} -- total crossings: {3}",
				levels.Sum(ll => ll.arr.Length),
				levels.Sum(ll => ll.arr.Sum(le => le.Lower.Length)),
				levels.Length,
				total_crossings());
		}
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public struct debug_layout_entry
	{
		public debug_layout_entry(layout_level LL, int ix_phys)
		{
			Debug.Assert(ix_phys >= 0 && ix_phys < LL.arr.Length);
			this.LL = LL;
			this.layout_ref.i_level = LL.i_level;
			this.layout_ref.ix_phys = ix_phys;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public layout_level LL;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public vref_ix layout_ref;

		[DebuggerDisplay("[{ix_phys}]", Name = "Physical Index")]
		public int ix_phys { get { return layout_ref.ix_phys; } }

		[DebuggerDisplay("{ix_logical}", Name = "Logical Index")]
		public int ix_logical { get { return LL.arr[layout_ref.ix_phys].ix_logical; } }

		[DebuggerDisplay("{i_level}", Name = "Level")]
		public int i_level { get { return layout_ref.i_level; } }

		[DebuggerDisplay("V{(int)vr}", Name = "Vertex")]
		public Vref vr { get { return LL.arr[layout_ref.ix_phys].vr; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int[] Upper { get { return LL.arr[layout_ref.ix_phys].Upper; } }

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		int[] Lower { get { return LL.arr[layout_ref.ix_phys].Lower; } }

		[DebuggerDisplay("Count: {Upper.Length}", Name = "Upper")]
		debug_layout_entry[] y_upper { get { return _upper().ToArray(); } }

		[DebuggerDisplay("Count: {Lower.Length}", Name = "Lower")]
		debug_layout_entry[] z_lower { get { return _lower().ToArray(); } }

		IEnumerable<debug_layout_entry> _upper()
		{
			var arr = Upper;
			for (int i = 0; i < arr.Length; i++)
				yield return new debug_layout_entry(LL.PrevLevel, arr[i]);
		}

		IEnumerable<debug_layout_entry> _lower()
		{
			var arr = Lower;
			for (int i = 0; i < arr.Length; i++)
				yield return new debug_layout_entry(LL.NextLevel, arr[i]);
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public String addr { get { return String.Format("[L{0}.{1}]", i_level, ix_phys); } }

		public override String ToString()
		{
			return String.Format("{0,8} {1} L{2}{{ {3,4} {4,4} }} {5}",
				this.addr,
				LL.arr[ix_phys].map_above_display(LL).PadLeft(20),
				this.i_level,
				ix_phys + "→" + this.ix_logical,
				"V" + (int)vr,
				LL.arr[ix_phys].map_below_display(LL));
		}
	};
}
